|
A heuristic function, or simply a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. == Shortest paths == For example, for shortest path problems, a ''heuristic'' is a function, defined on the nodes of a search tree, which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy best-first search and A * to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A * search will expand nodes that have the lowest value for , where is the (exact) cost of the path from the initial state to the current node. If is ''admissible'', i.e., if never overestimates the costs of reaching the goal, then A * will always find an optimal solution. The classical problem involving heuristics is the n-puzzle. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「heuristic function」の詳細全文を読む スポンサード リンク
|